This invention relates in general to galois field arithmetic and more specifically to a single implementation of a multi-dimensional galois field multiplier.
Galois Field arithmetic is a cyclic finite field arithmetic such that any operation performed on any two numbers within the filed, yields a number in the field, i.e. there is no operation which can be done on any two numbers within the field which yields a number outside of the field. Finite field arithmetic uses real numbers that consist of the range of numbers shown in Table 1 below. For example, the range of integers from 0 to 7(0,1,2,3,4,5,6,7) has a Galois Field representation or notation of GF(8) because the Galois Field has 8 elements, while the range of integers 0 to 1 has a Galois Field of GF(2) because it has only two elements, etc. In addition, digital systems transmit data in bits. Because bits are binary, they can only take on one of two values, either a 0 or a 1. Grouping these bits together to build a symbol is common in digital systems. These groupings are all based on a power of two. Table 1 lists the digital symbols vs. GF notation.
There are several ways of representing the numbers in the finite field of any given Galois Field. For example, the data shown on Table 2 shows the integer, binary and polynomial representations of the numbers of GF(8).
In addition, each Galois Field has one or more primitive polynomials which is analogous to a particular set of consecutive real integers which also has one or more prime numbers, depending upon how large is the particular set of consecutive integers. Primitive polynomials, p(x), are polynomials which are used to define the arithmetic functions for each field. For example, in Galois Field arithmetic, like arithmetic, certain mathematical properties exist such as laws of commutativity, associativity, etc. Therefore, when determining what is the sum or product of any two elements within a Galois Field, if after applying such laws, the sum or product will lie outside the Galois Field, that sum or product is divided by a predetermined primitive polynomial. In this way, the Galois Field is preserved. Table 3 lists the integer representation of all the primitive polynomials for GF(8) to GF(256).
As can be seen from the above table, there is only one primitive polynomial for GF(8) and GF(16), due to the smallness of the field, however, GF(128) has 9 primitive polynomials and GF(256) has 8 primitive polynomials. As mentioned previously, each of these integer representations has a corresponding polynomial representation. For example, one primitive polynomial, p(x) for GF(256) is 285, which corresponds to p(x)=x8+x4+x3+x2+1.
Multiplication in finite fields is easily computed using the polynomial format. For the following examples, GF(8) and p(x)=x3+x+1 are used to build the multiplication tables in Tables 4 and 5. The primitive polynomial is used to reduce or xe2x80x98foldxe2x80x99 the product or summation results back into the field. For example:
x2xc3x97x2=x4 
where x4 is not a member of the GF(8) field. The primitive polynomial, p(x), is then used in a polynomial division to generate the remainder of:
x4/p(x)=x4/x3+x+1=x2+x 
The same primitive polynomial is used to generate the entire multiplication table per GF, even if more than one primitive polynomial exists for a particular GF.
Galois Field (GF) multiplication is an important and necessary function, i.e. performed many times, in Reed-Solomon (RS) codes. RS codes are used in many communication applications such as satellites, modems, audio compact disks, and set-top boxes as a digital data transmission forward error correction tool. Each one of these applications has a different standard. Each standard defines a symbol size, a GF, and a primitive polynomial. Each application requires a unique GF multiplier or a GF multiplier which has a unique configuration to be created which will at least depend on the symbol size, the size of the Galois Field and the primitive polynomial used. There has never been a GF multiplier which could implement all the different standards in a cost efficient manner.
An implementation of a multi-dimensional Galois Field multiplier for Galois Fields from a GF(8) up to a GF(256) is disclosed. This GF multiplier is able to support many different communication standards such as standards with different symbol sizes, different GFs, and different primitive polynomials. The key to allow a single implementation of a GF multiplier to perform for all different GF sizes is to shift input operand B and primitive polynomial PP signals to the left and to shift the output ZO to the right, depending upon the size of the GF, as will be further described in the following paragraphs and shown in FIGS. 1, 3 and 6. The shifting of signals allows the MULT_XOR arrays to operate on all fields with the exact same hardware with a minimum delay of just two XOR gates per block. In other words, the critical path of each MULT_XOR block is just 2 XOR gates. The solution presented is a cost efficient multiplier configuration.